package leetcode

type ACTrie struct {
	next   map[rune]*ACTrie
	fail   *ACTrie
	length int
}

func NewACTrie() *ACTrie {
	return &ACTrie{
		next: make(map[rune]*ACTrie),
	}
}

func (t *ACTrie) insert(strs string) {
	var (
		i   int
		ok  bool
		str rune
		c   *ACTrie
		p   = t
	)

	for i, str = range strs {
		if c, ok = p.next[str]; !ok {
			c = NewACTrie()
			p.next[str] = c
		}
		p = c
	}
	c.length = i + 1
}

func (t *ACTrie) SetFail() {
	var (
		i       int
		ok      bool
		str     rune
		p, c, f *ACTrie
		queue   = []*ACTrie{t}
	)

	for i = 0; i < len(queue); i++ {
		p = queue[i]

		for str, c = range p.next {
			f = p.fail

			for {
				if f == nil {
					c.fail = t
					break
				}

				if c.fail, ok = f.next[str]; ok {
					break
				}

				f = f.fail
			}

			if len(c.next) > 0 {
				queue = append(queue, c)
			}
		}
	}
}

func (t *ACTrie) Query(strs string) int {
	var (
		i    int
		str  rune
		ok   bool
		p, r *ACTrie
		n    = t
	)
	for i, str = range strs {
		for {
			if n == nil {
				r = t
				break
			}

			if r, ok = n.next[str]; ok {
				break
			}

			n = n.fail
		}

		n = r
		for p = n; p != nil; p = p.fail {
			if p.length > 0 {
				return i + 1 - p.length
			}
		}
	}
	return -1
}

func strStr1(haystack string, needle string) int {
	if len(needle) == 0 {
		return 0
	}

	if len(haystack) == 0 {
		return -1
	}

	t := NewACTrie()
	t.insert(needle)
	t.SetFail()
	return t.Query(haystack)
}

func buildNext(needle string) []int {
	nLen := len(needle)
	next := make([]int, nLen)
	pos, cnd := 2, 0
	next[0] = -1

	for pos < nLen {
		if needle[pos-1] == needle[cnd] {
			cnd++
			next[pos] = cnd
			pos++
		} else if cnd > 0 {
			cnd = next[cnd]
		} else {
			pos++
		}
	}

	return next
}

func kmp(haystack string, needle string) int {
	nLen := len(needle)
	if nLen == 0 {
		return 0
	}

	hLen := len(haystack)
	if hLen == 0 {
		return -1
	}

	m, i, next := 0, 0, buildNext(needle)
	for m+i < hLen {
		if needle[i] == haystack[m+i] {
			if i == nLen-1 {
				return m
			}
			i++
			continue
		}

		if next[i] > -1 {
			m, i = m+i-next[i], next[i]
		} else {
			m++
			i = 0
		}

	}
	return -1
}
